package com.gxc.linkedList;

import java.util.Stack;

/**
 * 单调栈(转成求每个位置作为最小值的最大子数组和与该位置的乘积)
 * 定义:数组中累积和与最小值的乘积，假设叫做指标A。
 * 给定一个数组，请返回子数组中，指标A最大的值。
 */
public class MonotoneStack2 {

    public static void main(String[] args) {
        //                      0 1 2 3 4 5 6 7
        int[] array = new int[]{5,3,2,1,6,7,8,4};

        int result = max(array);
        System.out.println(result);
    }

    public static int max(int[] array) {
        int[][] result = monotoneStack2(array);
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < array.length; i++) {
            int sum = 0;
            for (int j=result[i][0]+1;j<result[i][1];j++) {
                if (j<0) continue;
                sum+=array[i]*array[j];
            }
            max = Math.max(max, sum);
        }
        return max;
    }

    private static int[][] monotoneStack2(int[] array) {
        int[][] result = new int[array.length][2];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                if (j==0) result[i][j] = -1;
                else result[i][j] = array.length-1;
            }
        }

        Stack<Integer> monotoneStack2 = new Stack<>();

        for (int i = 0; i < array.length; i++) {
            while (!monotoneStack2.isEmpty()) {
                if (array[monotoneStack2.peek()]>array[i]) {
                    Integer top = monotoneStack2.pop();
                    result[top][1] = i;
                    if (!monotoneStack2.isEmpty()) {
                        result[top][0] = monotoneStack2.peek();
                    }
                } else {
                    break;
                }
            }
            monotoneStack2.push(i);
        }

        while (!monotoneStack2.isEmpty()) {
            Integer top = monotoneStack2.pop();
            if (!monotoneStack2.isEmpty()) {
                result[top][0] = monotoneStack2.peek();
            }
        }

        return result;
    }
}
